(1) Field of Invention
The present invention relates to a method for particle swarm optimization and, more particularly, to a method for particle swarm optimization which utilizes a random walk process.
(2) Description of Related Art
The use of evolutionary heuristic optimization algorithms, such as genetic algorithms (GAs) and particle swarm optimization (PSO) algorithms, for a variety of applications is well known in the art. While these methods are effective, the present invention improves on what is currently known in the art by increasing the success rate of the PSO algorithm in addition to reducing the required computation.
PSO is a simple but powerful population-based algorithm that is effective for optimization of a wide range of functions as described by Eberhart and Shi (see Literature Reference No. 1). PSO models the exploration of a multi-dimensional solution space by a “swarm” of software agents, or particles, where the success of each agent has an influence on the dynamics of other members of the swarm. Each particle in a swarm of N particles resides in a multi-dimensional solution space. The positions of the particles represent candidate problem solutions. Additionally, each particle has a velocity vector that allows it to explore the space in search of an optimum of an objective function J.
FIG. 1 illustrates a prior art model of PSO depicting a multi-dimensional solution space 100 through which particles, for example particle Pi 102, travel in search of an optimum of an objective function (see Literature Reference No. 1). As described above, the positions of the particles represent vectors of multi-node parameter values in the solution space 100. In addition, each of the particles, including Pi 102, has a velocity vector 104 that allows it to explore the multi-dimensional solution space 100.
Although PSO is a relatively new area of research, literature exists which documents its efficiency and robustness as an optimization tool for high dimensional spaces (see Literature Reference Nos. 2 and 8). Both theoretical analysis and practical experience demonstrate that PSO converges on good solutions for a wide range of parameter values (see Literature Reference Nos. 3-7). The evolution of good solutions is stable in PSO because of the manner in which solutions are represented (i.e., small changes in the representation result in small changes in the solution). Furthermore, simulations have shown that the number of particles and iterations required are relatively low and scale slowly with the dimensionality of the solution space (see Literature Reference Nos. 9 and 10). However, the amount of computation required for PSO is still linearly proportional to the number of particles or the iterations required for a given problem. Therefore, reducing the number of particles or iterations required for a given problem can effectively reduce the computational cost of PSO. Thus, a continuing need exists for a method for PSO that efficiently reduces the number of iterations required to derive a solution.